/*
 * @lc app=leetcode.cn id=84 lang=golang
 *
 * [84] 柱状图中最大的矩形
 */

// 2-2. 优化2-1
// @lc code=start
func largestRectangleArea(heights []int) int {
	left, right := make([]int, len(heights)), make([]int, len(heights))

	for i := 0; i < len(heights); i++ {
		right[i] = len(heights)
	}

	stack := make([]int, 0)
	for i := 0; i < len(heights); i++ {
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
			right[stack[len(stack)-1]] = i
			stack = stack[:len(stack)-1]
		}

		if len(stack) > 0 {
			left[i] = stack[len(stack)-1]
		} else {
			left[i] = -1
		}
		stack = append(stack, i)
	}

	maxVal := 0
	for i := 0; i < len(heights); i++ {
		maxVal = max(maxVal, (right[i]-left[i]-1)*heights[i])
	}

	return maxVal
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// @lc code=end

// 2-1. 使用栈优化1-2，
// 每一次都往左右两边找，维护一个栈，把左右两边 遍历过的存起来
//
// 当栈顶元素大于等于当前元素时就弹出一个
// @lc code=start
func largestRectangleArea(heights []int) int {
	left, right := make([]int, len(heights)), make([]int, len(heights))

	stack := make([]int, 0)
	for i := 0; i < len(heights); i++ {
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
			stack = stack[:len(stack)-1]
		}

		if len(stack) > 0 {
			left[i] = stack[len(stack)-1]
		} else {
			left[i] = -1
		}
		stack = append(stack, i)
	}

	stack = make([]int, 0)
	for i := len(heights) - 1; i >= 0; i-- {
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
			stack = stack[:len(stack)-1]
		}

		if len(stack) > 0 {
			right[i] = stack[len(stack)-1]
		} else {
			right[i] = len(heights)
		}
		stack = append(stack, i)
	}

	maxVal := 0
	for i := 0; i < len(heights); i++ {
		height := heights[i]
		wide := right[i] - left[i] - 1
		maxVal = max(maxVal, wide*height)
	}

	return maxVal
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// @lc code=end

// 1-2. 暴力，枚举每根棒子 找左右第一个比它短的边界  超时
// @lc code=start
func largestRectangleArea(heights []int) int {
	maxVal := 0

	for i := 0; i < len(heights); i++ {
		left := i - 1
		right := i + 1
		for left >= 0 && heights[left] >= heights[i] {
			left--
		}

		for right < len(heights) && heights[right] >= heights[i] {
			right++
		}
		height := heights[i]
		wide := right - left - 1

		maxVal = max(maxVal, wide*height)
	}
	return maxVal
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// @lc code=end

// 1-1. 暴力，枚举左右边界 找中间最短的棒子  超时
// @lc code=start
func largestRectangleArea(heights []int) int {
	maxVal := math.MinInt64
	for i := 0; i < len(heights); i++ {
		for j := i; j < len(heights); j++ {
			maxVal = max(maxVal, (j-i+1)*minArr(heights[i:j+1]))
		}
	}
	return maxVal
}

func minArr(nums []int) int {
	minVal := nums[0]
	for i := 1; i < len(nums); i++ {
		minVal = min(minVal, nums[i])
	}
	return minVal
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// @lc code=end

